package LeetCode;
import java.util.*;
public class LeetCodeMain13 {
    Deque<String> res=new LinkedList<>();
    Map<String,Map<String,Integer>> map=new HashMap<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> t:tickets) {
            Map<String,Integer> temp;
            if (map.containsKey(t.get(0))){
                temp=map.get(t.get(0));
                temp.put(t.get(1),temp.getOrDefault(t.get(1),0)+1);
            }else {
                temp=new TreeMap<>();
                temp.put(t.get(1),1);
            }
            map.put(t.get(0),temp);
        }
        res.add("JFK");
        backtracking(tickets.size());
        return new ArrayList<>(res);
    }
    public  boolean backtracking(int ticketNum){
        if (res.size()==ticketNum+1){
            return true;
        }
        String last= res.getLast();
        if (map.containsKey(last)){
            for (Map.Entry<String,Integer> t:map.get(last).entrySet()) {
                int count=t.getValue();
                if (count>0){
                    res.add(t.getKey());
                    t.setValue(count-1);
                    if (backtracking(ticketNum)){
                        return true;
                    }
                    res.removeLast();
                    t.setValue(count);
                }
            }
        }
        return false;
    }
//    List<List<Integer >> list=new ArrayList<>();
//    public static Deque<String> res=new LinkedList<>();
//    public static Map<String, Map<String, Integer>> map=new HashMap<String,Map<String ,Integer>>();
//    public static List<String> findItinerary(List<List<String>> tickets) {
//        for (List<String> t: tickets) {
//            Map<String,Integer> temp;
//            if (map.containsKey(t.get(0))){
//                temp=map.get(t.get(0));
//                temp.put(t.get(1), temp.getOrDefault(t.get(1),0)+1);
//            }else {
//                temp = new TreeMap<>();//升序Map
//                temp.put(t.get(1), 1);
//            }
//            map.put(t.get(0), temp);
//        }
//        res.add("JFK");
//        backtracking(tickets.size());
//        return new ArrayList<>(res);
//    }
//    public static boolean backtracking(int ticketNum){
//        if (res.size()==ticketNum+1){
//            return true;
//        }
//        String last= res.getLast();
//        if (map.containsKey(last)){
//            for (Map.Entry<String,Integer> target:map.get(last).entrySet()) {
//                int count=target.getValue();
//                if (count>0){
//                    res.add(target.getKey());
//                    target.setValue(count-1);
//                    if (backtracking(ticketNum))return true;
//                    res.removeLast();
//                    target.setValue(count);
//                }
//            }
//        }
//        return false;
//    }

//    public static void main(String[] args) {
//        List<List<String>> list3=new ArrayList<>();
//        Scanner scanner=new Scanner(System.in);
//        for (int i = 0; i < 5; i++) {
//            List<String> list2=new ArrayList<>();
//            list2.add(scanner.next());
//            list2.add(scanner.next());
//            list3.add(list2);
//        }
//        System.out.println(findItinerary(list3));
//    }
}
